﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Xml.Linq;

namespace CodeTop.复习九月份
{
    public class Solution662
    {
        public int WidthOfBinaryTree(TreeNode root)
        {//层序遍历
            Queue<TreeNode> queue = new Queue<TreeNode>();
            Dictionary<TreeNode, int> map = new Dictionary<TreeNode, int>();//存节点和下标

            if (root == null)
            {
                return 0;
            }
            queue.Enqueue(root);
            map[root] = 1;//根节点编号1
            int res = 0;
            while (queue.Count > 0)
            {
                int count = queue.Count();
                res = Math.Max(res, count);
                int start = map[queue.Peek()];
                int end = 0;
                while (count > 0)
                {
                    TreeNode node = queue.Dequeue();
                    int indexP = map[node];

                    count--;
                    if (node.left != null)
                    {
                        queue.Enqueue(node.left);
                        map[node.left] = indexP * 2 + 1;
                    }
                    if (node.right != null)
                    {
                        queue.Enqueue(node.right);
                        map[node.right] = indexP * 2 + 1;
                    }
                    end = indexP;//存最后一个节点的编号
                }
                res = Math.Max(res, end - start + 1);
            }
            return res;
        }
    }
}